package cn.xaut.数组;

import java.util.HashMap;
import java.util.Map;

public class demo76 {

    // 检查当前字符串是否满足需要的字符串
    private boolean check(int[] have, int[] need) {

        for (int i = 0; i < need.length; i++) {
            if (need[i] > have[i])
                return false;
        }
        return true;
    }
    
    // 第三次挑战
    // 暴力解法
    /*public String minWindow3(String s, String t) {

        Map<Integer, Integer> map = new HashMap<>();
        int[] have = new int[128];
        int[] need = new int[128];
        
        for (char c : t.toCharArray())
            need[c] ++;
        int needLen = t.length();
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + needLen; j < s.length(); j++) {
                for (int k = i; k < j; k++) {
                    have[s.charAt(k)] ++;
                }
                if (check(have, need)) {
                    
                }
            }
        }
    }*/
    
    // 第二次挑战
    /*public String minWindow2(String s, String t) {

        int l = 0, r = -1;
        int[] freq = new int[128];
        for (char c : t.toCharArray())
            freq[c] ++;

        int len = s.length();
        
        while (l < len) {
            ++ r;
            if (r < len && freq[s.charAt(r)] > 0) {
                
            }
        }
    }*/

        // 挑战失败
    public String minWindow(String s, String t) {

        int[] freq = new int[128];
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        int l = 0, r = 0;
        int diff = t.length();
        for (char c : t.toCharArray())
            freq[c] ++;

        String str = "";
        int strLen = Integer.MAX_VALUE;
        int[] copy = new int[128];
        for (int i = 0; i < freq.length; i++) 
            copy[i] = freq[i];

        while (r < ss.length) {
            
            while (diff > 0) {
                if (r < ss.length && copy[ss[r]] > 0) {
                    copy[ss[r]] --;
                    diff--;
                }
                r++;
            }

            String a = s.substring(l, r);
            if (a.length() < strLen) {
                strLen = a.length();
                str = a;
            }

            copy[ss[l]] ++;
            l ++;
            diff ++;
            
            while (l < r && freq[ss[l]] == 0)
                l ++;
        }
        
        return str;
    }

    public static void main(String[] args) {

//        System.out.println(new demo76().minWindow("ADOBECODEBANC", "ABC"));//BANC
    }
}
